# 109. 分考场(好题, 图着色问题)
# https://www.lanqiao.cn/problems/109/learning/?page=1&first_category_id=1&second_category_id=3&contain_answer=true
# Date: 2025/2/8
from collections import defaultdict
from leetcode import test_function


def exam_room_alloc(edges):
    """
    图着色问题: 即一个平面区域被划分为多个不同的区域, 要求对所有区域着色, 且相邻的区域之间不能使用相同的颜色, 求最少需要多少种颜色
    """

    # 构建邻接表
    graph = defaultdict(list)
    for n1, n2 in edges:
        graph[n1].append(n2)
        graph[n2].append(n1)
    n = len(graph.keys())
    if n == 0:
        return 0
    node_colors = defaultdict(int)  # 记录节点的着色情况 1:1 -> 表示节点1使用的颜色是1
    min_colors = float('inf')

    def backtrack(current_node: int, used_color_count):
        nonlocal min_colors, n
        if current_node == n + 1:
            min_colors = min(min_colors, used_color_count)
            return

        # 获取当前节点的已着色邻居颜色
        used_colors = set()
        for neighbor in graph[current_node]:
            if neighbor in node_colors:
                used_colors.add(node_colors[neighbor])

        # 尝试现有颜色（剪枝：只在可能改善结果时尝试）
        for color in range(1, used_color_count + 1):
            if color not in used_colors and color < min_colors:
                node_colors[current_node] = color
                backtrack(current_node + 1, used_color_count)
                del node_colors[current_node]

        # 尝试新颜色（剪枝：只在可能改善结果时尝试）
        new_color = used_color_count + 1
        if new_color < min_colors:
            node_colors[current_node] = new_color
            backtrack(current_node + 1, new_color)
            del node_colors[current_node]

    backtrack(1, 1)  # 从节点开始处理，初始颜色数为1
    return min_colors


def exam_room_alloc_opt(edges):
    """优化的方法
    主要优化在于按照节点的度数(degree)的降序来处理所有节点, 优先处理邻居多的节点, 这样就可以减少少递归的次数, 达到剪枝的目的"""
    graph = defaultdict(list)
    nodes_set = set()
    for n1, n2 in edges:
        graph[n1].append(n2)
        graph[n2].append(n1)
        nodes_set.add(n1)
        nodes_set.add(n2)
    if not nodes_set:
        return 0

    # 将节点转换为列表，并按节点度（约束数,degree）降序排序，
    # 这样高约束节点会先着色，更有助于剪枝
    nodes = list(nodes_set)
    nodes.sort(key=lambda node: len(graph[node]), reverse=True)

    # 得到初始上界，有助于剪枝
    min_colors = len(nodes)

    # 记录当前着色方案 1:1 -> 表示节点1使用的颜色是1
    node_colors = {}

    def backtrack(index, used_color_count):
        """
        index: 当前着色节点在 nodes 列表中的索引
        used_color_count: 当前已使用的颜色数
        """
        nonlocal min_colors, node_colors

        # 若所有节点都已着色，更新最小颜色数
        if index == len(nodes):
            min_colors = min(min_colors, used_color_count)
            return

        # 剪枝：如果当前已使用的颜色数已经达到或超过最优解，则无需继续
        if used_color_count >= min_colors:
            return

        node = nodes[index]
        # 收集该节点已着色邻居的颜色
        neighbors_color = set()
        for neighbor in graph[node]:
            if neighbor in node_colors:
                neighbors_color.add(node_colors[neighbor])

        # 尝试使用已有的颜色
        for color in range(1, used_color_count + 1):
            if color not in neighbors_color:
                node_colors[node] = color
                backtrack(index + 1, used_color_count)
                """del关键字
                用于删除对象引用，从而释放内存。
                当一个对象的引用被删除时，如果这个对象没有其他的引用指向它，那么这个对象就会被 Python 的垃圾回收机制回收掉，
                释放其占用的内存空间。
                """
                del node_colors[node]

        # 尝试使用新颜色，前提是新颜色数仍小于当前最优解
        new_color = used_color_count + 1
        if new_color < min_colors:
            node_colors[node] = new_color
            backtrack(index + 1, new_color)
            del node_colors[node]

    # 从第 0 个节点开始，初始时还未使用任何颜色
    backtrack(0, 0)
    return min_colors


if __name__ == '__main__':
    # n = int(input())
    # m = int(input())
    # inp = []
    # for i in range(m):
    #     inp.append(tuple(map(int, input().split())))
    edges = []
    with open("../data/109.in", "r") as file:
        n = int(file.readline())
        m = int(file.readline())
        for i in range(m):
            edges.append(tuple(map(int, file.readline().split())))

    inp = [{"edges": [(1, 2), (1, 6), (1, 7), (2, 3), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 6), (6, 7)]},
           {"edges": [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5)]},
           {"edges": edges},
           ]
    out = [3, 4, 8]
    test_function(exam_room_alloc, inp, out)
    test_function(exam_room_alloc_opt, inp, out)
